package com.example.origin.demo.demo;

import org.springframework.web.bind.annotation.GetMapping;
import org.springframework.web.bind.annotation.RequestMapping;
import org.springframework.web.bind.annotation.RestController;

import java.util.*;

/**
 * Description: 十万个数据,找出重复次数最多的十个数据并打印
 *
 * @Author Fann
 * @Data 2018/11/14
 */
@RequestMapping("NumRepeatDemo")
@RestController
public class NumRepeatDemo {

    @GetMapping("test")
    public void test(){
        final int NUM = 100000;//十万个
        int t = 0;
        Random random = new Random();
        HashMap<Integer, Integer> hashMap = new HashMap<Integer, Integer>(NUM);//key:数据 value:出现次数
        //模拟十万个数据
        while (t < NUM) {
            Integer i = random.nextInt(1000);
            if (hashMap.containsKey(i)) {  //如果存在,出现次数+1,不存在出现次数为1
                hashMap.put(i, hashMap.get(i) + 1);
            } else {
                hashMap.put(i, 1);
            }
            t++;
        }

        //用来存储最终的十个结果,优先级队列  小根堆形式,最小的在堆顶.
        PriorityQueue<Map.Entry<Integer, Integer>> priorityQueue =
                new PriorityQueue<Map.Entry<Integer, Integer>>(10, new Comparator<Map.Entry<Integer, Integer>>() {
                    @Override
                    public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
                        return o1.getValue() - o2.getValue();
                    }//o1-o2 可以这样理解,如果返回正数,说明o1-o2>0.返回负数说明o1-o2<0
                });


        //通过hashmap的entrySet进行遍历.
        Iterator<Map.Entry<Integer, Integer>> iterator = hashMap.entrySet().iterator();
        //先随便放10个,priorityQueue会自动排序
        for (int i = 0; i < 10; i++) {
            priorityQueue.add(iterator.next());
        }

        //再放其他的
        while (iterator.hasNext()) {
            Map.Entry<Integer, Integer> curEntry = iterator.next(); //当前遍历的.
            Map.Entry<Integer, Integer> topEntry = priorityQueue.peek(); //获得队列中最小的那一个.

            if (curEntry.getValue() > topEntry.getValue()) {
                priorityQueue.remove(topEntry);
                priorityQueue.add(curEntry);
            }
        }

        //打印结果
        Iterator<Map.Entry<Integer, Integer>> iterator2 = priorityQueue.iterator();
        while (iterator2.hasNext()) {
            Map.Entry<Integer, Integer> entry = iterator2.next();
            System.out.println(entry.getKey() + ":出现了" + entry.getValue() + "次");
        }
    }
}